/**
 * 86. 分隔链表
 * https://leetcode-cn.com/problems/partition-list/
 */
public class Solutions_86 {
    public static void main(String[] args) {
        int[] arr = {1, 4, 3, 2, 5, 2};
        int x = 3;  // output: {1, 2, 2, 4, 3, 5}

        ListNode head = MyLinkedListUtils.ArrayToListNode(arr);
        ListNode result = partition(head, x);
        System.out.println(MyLinkedListUtils.ListNodeToString(result));
    }

    public static ListNode partition(ListNode head, int x) {
        ListNode left = new ListNode(-1);
        ListNode tempLeft = left;
        ListNode right = new ListNode(-1);
        ListNode tempRight = right;
        // 遍历链表
        for (ListNode node = head; node != null; node = node.next) {
            if (node.val < x) {
                // 小于 x 的结点，链接到 tempLeft 中
                tempLeft.next = node;
                tempLeft = tempLeft.next;
            } else {
                // 大于等于 x 的结点，链接到 tempRight 中
                tempRight.next = node;
                tempRight = tempRight.next;
            }
        }
        // 链接两个链表
        tempRight.next = null;
        tempLeft.next = right.next;
        return left.next;
    }
}
